class Solution:
    def countBits(self, n):
        ans = [0] * (n+1)
        for i in range(1, n+1):
            ans[i] = ans[i >> 1] + (i & 1)
        return ans
if __name__ == '__main__':
    s = Solution()
    print(s.countBits(5))

# 一个数的二进制 1 的个数，可以由它“右移一位的结果”加上它的最低位是否为 1 推导出来